\newcommand\red[1]{\textcolor{red}{#1}}
\newcommand\blue[1]{\textcolor{blue}{#1}}
\newcommand\green[1]{\textcolor{green}{#1}}
\newcommand\magenta[1]{\textcolor{magenta}{#1}}


\section{Verschlüsselung - Stromchiffren}

In diesem Kapitel beschäftigen wir uns mit den Blockchiffren und deren Betriebsmodi ECB, CBC, OFB und CFB.

Eine Blockchiffre permutiert einen Klartext zu einem Chiffrat.
Allgemein arbeitet eine Blockchiffre auf einer Blocklänge $n \in \mathbb N$ und einem Alphabet $\Sigma$.
Der Klartextraum ($\mathcal P$) und Schlüsseltextraum ($\mathcal C$) ist definiert als $\mathcal P = \mathcal C = \Sigma^n$.
Der Schlüssel $\pi \in S(\Sigma^n)$ hat die Verschlüsselungsfunktion:
\begin{center}
$E_\pi : \Sigma^n \rightarrow \Sigma^n, \textbf{v} \mapsto \pi(\textbf{v})$.
\end{center}
Entschlüsselt wird entsprechend:
\begin{center}
$D_\pi : \Sigma^n \rightarrow \Sigma^n, \textbf{v} \mapsto \pi^{-1}(\textbf{v})$.
\end{center}
Der Schlüsselraum enthält $(|\Sigma|^n)!$ viele Elemente.

Gebräuchlich ist es die mehrfach hintereinander zu verschlüsseln, um die Sicherheit zu erhöhen.
Ein Klartext $p$ wir dabei folgendermaßen verschlüsselt:
\begin{center}
$c=E_{k_1}(D_{k_2}(E_{k_3}(p)))$.
\end{center}

\subsection{Electronic Codebook Mode - ECB}
Alphabet $\Sigma$, Blocklänge $n$, Schlüsselraum $\mathcal K$, Verschlüsselungsfunktion $E_k$ und Entschlüsselungsfunktion $D_k$ mit $k \in \mathcal K$

\begin{figure}[htbp]
	\centering
	\includegraphics[width=11cm]{ex1/gfx/ecb.png}
	\caption{ECB mode}
	\label{fig:ECB}
\end{figure}

Der Klartext $m$ wird in $n$ Blöcke aufgeteilt und wie in Bild \ref{fig:ECB} dargestellt wird jeder Block zu $m_j$ mit $E_e$ zu $c_j$ verschlüsselt.
Das Gleiche gilt umgekehrt, nur das nun $c_j$ zu $m_j$ mit $d$ entschlüsselt wird.

\subsubsection{Nachteile}
\begin{itemize}
  \item Gleiche Klartextblöcke werden auf gleiche Chiffretextblöcke abgebildet. Das erzeugt Regelmäßigkeiten, die der Angreifer ausnutzen kann.
  \item Ein Angreifer kann die Nachricht ändern (einfügen, löschen, vertauschen), da jeder Block unabhängig von anderen ist. Damit ist der ECB Mode schlecht für lange Nachrichten.
\end{itemize}

\subsubsection{Beispiel}
Ein Beispiel einer Bitpermutation:
$\Sigma = \{0,1\}^4 \rightarrow \{0,1\}^4, b_1b_2b_3b_4 \mapsto b_{\pi(1)}b_{\pi(2)}b_{\pi(3)}b_{\pi(4)}$\\
Der Klartext $m$ sei 
\begin{center}
$m = 1011\text{ }0001\text{ }0100\text{ }101\textcolor{red}{0}$.
\end{center} 
Der letzte Block wird ergänzt (rot markiert), da er nicht die erforderliche Länge 4 besitzt.
Man hat also folgende Blöcke:
\begin{center}
$m_1 = 1011,\text{ }m_2 = 0001,\text{ }m_3 = 0100,\text{ }m_1 = 1010$.
\end{center}
Der Schlüssel ist:
\begin{center}
$ \pi = 
\begin{pmatrix} 
1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 
\end{pmatrix}
$
\end{center}
Damit ist das Chiffrat:
\begin{center}
$c_1 = E_{\pi}(m_1) = 0111,\text{ }c_2 = E_{\pi}(m_2) = 0010,\text{ }c_3 = E_{\pi}(m_3) = 1000,\text{ }c_4 = E_{\pi}(m_4) = 0101$.

$c = c_1 \circ c_2 \circ c_3 \circ c_4 = 0111001010000101$
\end{center}

\subsection{Cipherblock Chaining Mode - CBC}
Alphabet $\Sigma = \{0,1\}$, Blocklänge $n$, Schlüsselraum $\mathcal K$, Verschlüsselungsfunktion $E_k$ und Entschlüsselungsfunktion $D_k$ mit $k \in \mathcal K$
Weiterhin sei die Verknüpfung $\oplus$ als bitweises XOR (Exklusiv-Oder) definiert.
\begin{center}
$\oplus : \{0,1\}^2 \rightarrow \{0,1\}, (b,c) \mapsto b \oplus c$
	\begin{table}[htbp]
	\centering
	\begin{tabular}{|c|c||c|}
	\hline
	$b$ & $c$ & $b \oplus c$ \\
	\hline
	0 & 0 & 0 \\
	1 & 0 & 1 \\
	0 & 1 & 1 \\
	1 & 1 & 0 \\
	\hline
	\end{tabular}
	\label{tab:XOR}
	\end{table}
\end{center}
Nach \buchmann{4.8.2} funktioniert das Verfahren nun so (vergleiche Abbildung \ref{fig:CBC}):
\begin{figure}[htbp]
	\centering
	\includegraphics[width=11cm]{ex1/gfx/cbc.png}
	\caption{CBC mode}
	\label{fig:CBC}
\end{figure}
\begin{itemize}
  \item Wähle einen Initialvektor $IV \in \Sigma^n$.
  \item Teile den Klartext $m$ in Blöcke der Länge $n$ zu $m = m_1 \circ m_2 \circ \ldots \circ m_t$ auf.
  \item Verschlüssele einen Klartextblock $m_j$ mit:\\
  		$c_0 = IV,\text{ }c_j=E_e(c_{j-1} \oplus m_j),\text{ }1 \leq j \leq t$.
  \item Entschlüsseln des Blocks $c_j$ geht mit:\\
  		$c_0 = IV,\text{ }m_j=c_{j-1} \oplus D_d(c_j),\text{ }1 \leq j \leq t$.
\end{itemize}

\subsubsection{Vor- und Nachteile}
\begin{itemize}
  \item Gleiche Klartextblöcke werden unterschiedlich verschlüsselt, wenn sich der Initialisierungsvektor ändert.
  \item Der Folgeblock hängt vom Vorgänger ab. 
  Ändert ein Angreifer einen Block ab, ändern sich die anderen auch und der Klartext ergibt keinen Sinn mehr. 
  Angriffe können erkannt werden.
  \item Übertragungsfehler in einem Block $c_j$ haben nur Auswirkungen auf dne Klartext $m_j$ und $m_{j+1}$.
  Das bedeutet, dass der Initialisierungsvektor bei Sender und Empfänger unterschiedlich sein können. 
  Der erste Klartextblock wird dann verworfen und der Nachfolger wieder richtig berechnet.
  \item Eignet sich für lange Nachrichten, aber der Empfänger muss auf alle Schlüsseltextblöcke warten bevor er entschlüsseln kann.
\end{itemize}

\subsubsection{Beispiel}
Der Klartext $m$ sei wieder 
\begin{center}
$m_1 = 1011,\text{ }m_2 = 0001,\text{ }m_3 = 0100,\text{ }m_4 = 1010$.
\end{center}
Der Schlüssel ist:
\begin{center}
$ \pi = 
\begin{pmatrix} 
1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 
\end{pmatrix}
$
\end{center}
Der Initialisierungsvektor $IV$ ist $IV=1010$.
Damit ist also der Ablauf wie folgt:
\begin{itemize}
  \item $c_0=1010$
  \item $c_1=E_\pi(c_0 \oplus m_1) = E_\pi(0001) = 0010$
  \item $c_2=E_\pi(c_1 \oplus m_2) = E_\pi(0011) = 0110$
  \item $c_3=E_\pi(c_2 \oplus m_3) = E_\pi(0010) = 0100$
  \item $c_4=E_\pi(c_3 \oplus m_4) = E_\pi(1110) = 1101$
\end{itemize}

Das Ergebnis ist: $c = 0010\text{ }0110\text{ }0100\text{ }1101$.\\
Die Entschlüsselung verläuft analog:

\begin{itemize}
  \item $c_0=1010$
  \item $m_1=c_0 \oplus E_\pi^{-1}(c_1) = 1010 \oplus 0001 = 1011$
  \item $m_2=c_1 \oplus E_\pi^{-1}(c_2) = 0010 \oplus 0011 = 0001$
  \item $m_3=c_2 \oplus E_\pi^{-1}(c_3) = 0110 \oplus 0010 = 0100$
  \item $m_4=c_3 \oplus E_\pi^{-1}(c_4) = 0100 \oplus 1110 = 1010$
\end{itemize}

Das Ergebnis ist: $m = m_1 \circ m_2 \circ m_3 \circ m_4 = 1011\text{ }0001\text{ }0100\text{ }1010$. 

\subsection{Cipher Feedback Mode - CFB}
\begin{figure}[htbp]
	\centering 
	\includegraphics[width=11cm]{ex1/gfx/cfb.png}
	\caption{CFB mode}
	\label{fig:CFB}
\end{figure}
\begin{itemize}
  \item Wähle einen Initialvektor $IV \in \Sigma^n$.
  \item Wähle ein $r \in \mathbb N, 1 \leq r \leq n$
  \item Teile den Klartext $m$ in Blöcke der Länge $r$ zu $m = m_1 \circ m_2 \circ \ldots \circ m_u$ auf.
  \item Verschlüssele einen Klartextblock $m_j, 1 \leq j \leq u$ mit:
  \begin{enumerate}
    \item Im ersten Schritt: $I_1 = IV$
    \item $O_j = E_k(I_j)$
    \item $t_j$ auf die ersten $r$-Bits von $O_j$ setzen
    \item $c_j = m_j \oplus t_j$
    \item $I_{j+1} = 2^rI_j+c_j \mod 2^n$
  \end{enumerate}
  \item Der Schlüsseltext ist dann $c = c_1 \circ c_2 \circ \ldots \circ c_u$
  \item Entschlüsseln des Blocks $c_j$ ist anaolog. Lediglich Schritt 4 ist anders:
  \begin{enumerate}
    \item Im ersten Schritt: $I_1 = IV$
    \item $O_j = E_k(I_j)$
    \item $t_j$ auf die ersten $r$-Bits von $O_j$ setzen
    \item $ m_j = c_j \oplus t_j$
    \item $I_{j+1} = 2^rI_j+c_j \mod 2^n$
  \end{enumerate}
\end{itemize}

\subsubsection{Vor- und Nachteile}
\begin{itemize}
  \item Sender und Empfänger können simultan $t_{j+1}$ bestimmen, da dazu lediglich ein $c_j$ bekannt sein muss. 
  Das setzt sich mit den weiteren $t_j$ so fort.
  \item Der Übertragungsfehler setzt sich so lange fort, bis die fehlerhaften Bits aus dem Vektor $I_j$ rausgeschoben wurden.
\end{itemize}

\subsubsection{Beispiel}
Der Klartext $m$ sei mit $r=3$ wie folgt definiert: 
\begin{center}
$m_1 = 101,\text{ }m_2 = 100,\text{ }m_3 = 010,\text{ }m_4 = 100,\text{ }m_4 = 101$.
\end{center}
Der Schlüssel ist:
\begin{center}
$ \pi = 
\begin{pmatrix} 
1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 
\end{pmatrix}
$
\end{center}
Der Initialisierungsvektor $IV$ ist $IV=\red{1010}$.
Damit ist also der Ablauf wie folgt:
\begin{center}
	\begin{table}[htbp]
	\centering
	\begin{tabular}{|c||c|c|c|c|c|}
	\hline
	$j$ & $I_j$ & $O_j$ & $t_j$ & $m_j$ & $c_j$ \\
	\hline\hline
	1 & \red{1010} & \magenta{010}1 & \magenta{010} & 101 & 111 \\
	2 & 011\green{1} & 1110 & 111 & 100 & \green{011} \\
	3 & \green{1011} & 0111 & 011 & 010 & 001 \\
	4 & 1001 & 0011 & 001 & 100 & 101 \\
	5 & 1101 & 1011 & 101 & 101 & 000 \\
	\hline
	\end{tabular}
	\label{tab:CFBEncode}
	\end{table}
\end{center}
In der Tabelle \ref{tab:CFBEncode} sind die Schritte farbig markiert. Rot ist der Initialisierungsvektor.
Magenta ist Abschneiden der ersten $r$-Bits ($r=3$ in dem Fall) und grün ist das Bilden von $I_{j+1}$ mit $j=2$.
$I_{j+1}$ ist dann folgendermaßen für $j=2$ zu bilden:

$I_{j+1} = 2^rI_j+c_j \mod 2^n$,

$I_{2+1} = 2^3I_2+c_2 \mod 2^4 = 2^3*011\textbf{1} + \textbf{011} \mod 2^4 = 011\textbf{1000} + \textbf{011} \mod 2^4 = 011\textbf{1011} \mod 2^4 = \textbf{1011}$.

Die Entschlüsselung läuft analog und sparen wir uns hier.

\subsection{Output Feedback Mode - OFB}
Für den OFB Mode gelten die gleichen Voraussetzungen wie im CFB Mode. 
Der einizge Unterschied ist die Berechnung von  $I_{j+1}$.
\begin{figure}[htbp]
	\centering 
	\includegraphics[width=11cm]{ex1/gfx/ofb.png}
	\caption{OFB mode}
	\label{fig:OFB}
\end{figure}
\begin{itemize}
  \item Wähle einen Initialvektor $IV \in \Sigma^n$.
  \item Wähle ein $r \in \mathbb N, 1 \leq r \leq n$
  \item Teile den Klartext $m$ in Blöcke der Länge $r$ zu $m = m_1 \circ m_2 \circ \ldots \circ m_u$ auf.
  \item Verschlüssele einen Klartextblock $m_j, 1 \leq j \leq u$ mit:
  \begin{enumerate}
    \item Im ersten Schritt: $I_1 = IV$
    \item $O_j = E_k(I_j)$
    \item $t_j$ auf die ersten $r$-Bits von $O_j$ setzen
    \item $c_j = m_j \oplus t_j$
    \item $I_{j+1} = O_j$
  \end{enumerate}
  \item Der Schlüsseltext ist dann $c = c_1 \circ c_2 \circ \ldots \circ c_u$
\end{itemize}

\subsubsection{Vor- und Nachteile}
\begin{itemize}
  \item Sender und Empfänger können wieder simultan $_{j+1}$ bestimmen, da dazu lediglich ein $c_j$ bekannt sein muss. 
  Das setzt sich mit den weiteren $t_j$ so fort.
  \item Klartextblöcke hängen nicht vom Vorgängerblock, sondern nur von der Position ab. 
  Texte im OFB Mode können damit leichter manipuliert werden als im CBC Mode.
\end{itemize}

\subsubsection{Beispiel}
Der Klartext $m$ sei mit $r=3$ wie folgt definiert: 
\begin{center}
$m_1 = 101,\text{ }m_2 = 100,\text{ }m_3 = 010,\text{ }m_4 = 100,\text{ }m_4 = 101$.
\end{center}
Der Schlüssel ist:
\begin{center}
$ \pi = 
\begin{pmatrix} 
1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 
\end{pmatrix}
$
\end{center}
Der Initialisierungsvektor $IV$ ist $IV=\red{1010}$.
Damit ist also der Ablauf wie folgt:
\begin{center}
	\begin{table}[htbp]
	\centering
	\begin{tabular}{|c||c|c|c|c|c|}
	\hline
	$j$ & $I_j$ & $O_j$ & $t_j$ & $m_j$ & $c_j$ \\
	\hline\hline
	1 & \red{1010} & \magenta{010}1  & \magenta{010} & 101 & 111 \\
	2 & 0101 & \green{1010} & 101 & 100 & 001 \\
	3 & \green{1010} & 0101 & 010 & 010 & 000 \\
	4 & 0101 & 1010 & 101 & 100 & 001 \\
	5 & 1010 & 0101 & 010 & 101 & 111 \\
	\hline
	\end{tabular}
	\label{tab:CFBEncode}
	\end{table}
\end{center}

Die Entschlüsselung läuft analog und sparen wir uns hier.

Wichtig hier ist folgender Sachverhalt:\\
Falls der Schlüssel k (in diesem Fall mit $\pi$ bezeichnet) mehrfach verwendet werden soll, muss $IV$ unterschiedlich gewählt werden,
da es sonst zu Regelmäßigkeiten in den Schlüsselstrings $t_j$ kommt.
Der Angreifer kann dann nämlich $m_j'$ bestimmen, falls $c_j$ und $c_j'$ bekannt ist:

$c_j = m_j \oplus t_j$,\\
$c_j' = m_j' \oplus t_j$,\\
$c_j \oplus c_j' = m_j \oplus m_j'$.

\newpage
\subsection{Stromchiffre}
Die im Buchmann durchgesprochene Stromchifffre auf LFSR-Basis besteht aus folgenden Elementen:
\begin{itemize}
	\item Schlüssel $k=(k_1,\ldots,k_n)$
	\item Wort $w=\sigma_1\ldots\sigma_m$
	\item Schlüsselstrom $z_1,z_2,\ldots,z_m$ Der sich aus $z_i = ki, 1 \leq i \leq n$ und $z_i= \sum\limits_{j=1}^n
	c_jz_{i-j} \tmod 2, n < i <m$ zusammensetzt. $c_1,\ldots,c_n$ sind dabei für dieses Verfahren fest gewählte Bits. Hier
	ist zu beachten, dass $c$ und $z$ quasi entgegengesetzt zueinander verrechnet werden!
	\begin{figure}[htbp]
	\centering
	\includegraphics[width=11cm]{ex1/gfx/stromchiffre.png}
	\caption{Erstellung des Schlüsselstroms}
	\label{fig:Stromchiffre}
\end{figure}
\end{itemize}
Die Ver- und Entschlüsselung des Wortes $w$ funktioniert dann wie folgt $E_k(w) = \sigma_1 \xor z_1,\ldots,\sigma_m \xor
z_m$ bzw. $D_k(w) = \sigma_1 \xor z_1,\ldots,\sigma_m \xor
z_m$.


\subsubsection{Beispiel}
\begin{itemize}
	\item Schlüssel $k= (1,0,0,0)$
	\item Wort $w= (1,0,1,1,0,1,0,1,1)$
	\item $c = (0,0,1,1)$
\end{itemize}

Aus $k$ und $c$ lässt sich wie oben beschrieben der Schlüsselstrom $z = (1,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1,0,0,0,\ldots)$
bilden. Dieser ist periodisch und hat die Periodenlänge 15. Nun wird das Wort $w$ über $\xor$ mit dem
Schlüsselstrom $z$ verrechnet. Das Ergebnis ist $E_k(w)=(0,0,1,1,1,1,0,0,0)$.
